package com.jerry.utils;

import java.util.Scanner;

public class DFS {

    private static int N = 10; //控制代码内数组大小
    private static int n; //定义值 让用户输入
    private static int[] arr = new int[N];  //创建一个新的数组
    private static int[] res = new int[N];  // 结果数组
    private static boolean[] isUsed = new boolean[N]; //记录已经使用过的数字


    public static void dfs(int x){
        if(x == n){ //当x=n使唤 表示一个排列已经完成 打印结果
            for (int i =0; i<n ;i++){
                System.out.println(res[i] + " ");
            }
            System.out.println();
            return;
        }
        //遍历所有数
        for (int i=0; i< n; i++){
            if(!isUsed[i]){ //如果没有使用 继续尝试使用它
                res[x] = arr[i]; //将这个数添加到结果数组
                isUsed[i] =true; //标记这个数已经使用过
                dfs(x+1); //继续搜索下一个数
                isUsed[i] =false; //撤销选择尝试其他可能性
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0;i<n;i++){
            arr[i] = i+1;
        }
        dfs(n);
    }
}
